package net.lainiao.leetcode;

import java.util.Arrays;

public class LintCode130 {
    ///最小堆
    public static void main(String[] args) {
        int[] arr={3,2,1,4,5};
        LintCode130 code130=new LintCode130();
        code130.heapify(arr);
        String str= Arrays.toString(arr);
        System.out.println(str);
    }

    public void heapify(int[] A) {
        int len=A.length;
        int start=len/2-1;
        for(int i=start;i>=0;i--){
            justheap(i,A);
        }
    }

    public void justheap(int index,int[] A){
        int leftIndex=index*2+1;
        int rightIndex=index*2+2;
        int minIndex=index;
        int len=A.length;
        if(leftIndex<len&&A[index]>A[leftIndex]){
            minIndex=leftIndex;
        }
        if(rightIndex<len&&A[minIndex]>A[rightIndex]){
            minIndex=rightIndex;
        }
        if(minIndex==index){
            return ;
        }
        int tem=A[minIndex];
        A[minIndex]=A[index];
        A[index]=tem;
        justheap(minIndex,A);
    }
}
